/*
 *https://leetcode.cn/problems/find-if-path-exists-in-graph/
 *547. 省份数量
 *medium 吴朝泽 2024.9.25
 *并查集
 模板题，因为本题求的连通图的数量，模板中有着找到连通图个数的函数，创建对象调用即可
 注意 isConnected[i][j] == 1 表示第 i 个城市和第 j 个城市直接相连，若判断是 1 则合并两个点
*/

class union_find {
public:
    // 构造从 0 到 n - 1 的节点
    union_find(int n) : n(n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    // 合并两个节点
    void pair(int index1, int index2) {
        parent[find(index2)] = find(index1);
    }
    // 找到根节点
    int find(int index) {       // 递归函数，找根节点的同时进行路径压缩
        if (parent[index] != index) {
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }
    // 判断连接性
    bool check(int index1, int index2) {
        return find(index1) == find(index2);
    }
    // 返回连通图的数量
    int groupCount() {      // 集合去重得到连通图的数量
        unordered_set<int> us;
        for (int i = 0; i < n; ++i) us.emplace(find(i));
        return us.size();
    } 
private:
    int *parent, n;
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        union_find uf(isConnected.size());

        //注意二维数组的遍历
        for(int i = 0; i < isConnected.size(); ++i)
        {
            for(int j = 0; j < isConnected[0].size(); ++j)
            {
                if(isConnected[i][j] == 1)
                    path.pair(i , j);
            }
        }
            
        return path.groupCount();
    }
};